package cn.lintcode;

/* ━━━━━━如来保佑━━━━━━
 * 　　   へ　　　　　／|
 * 　　　/＼7　　　∠＿/
 * 　　/　│　　／　／
 * 　　│　Z＿,＜　／　　/`ヽ
 * 　　│　　　　　ヽ　　/　　〉
 * 　　Y　　　　　`　/　　/
 * 　　ｲ●　､　●　　⊂⊃〈　　/
 * 　　()　へ　　　　|　＼〈
 * 　　　>ｰ､_　ィ　│／／
 * 　　/へ　　/　ﾉ＜|＼＼
 * 　　ヽ_ﾉ　　(_／　│／／
 * 
 * ━━━━━━永无BUG━━━━━━
 * @user tianxinxing
 * @date 2019/1/4
 */
//lintcode 13题
/*
* 对于一个给定的 source 字符串和一个 target 字符串，
* 你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
* */
public class strFInd {
    /**
     * @param source:
     * @param target:
     * @return  return the index
     */
    public int strStr(String source, String target) {
        // Write your code here
        //target字符串生成kmp的数组
        if(target.length() == 0){
            return 0;
        }
        if(source.length() < target.length()){
            return -1;
        }


        char[] ss = source.toCharArray();
        char[] ms = target.toCharArray();
        int si = 0;
        int mi = 0;
        if(source.length() == target.length()){
            while(si<ss.length){
                if(ss[si] != ms[mi]){
                    return -1;
                }
                si++;
                mi++;
            }
            return 0;
        }
        if(ms.length == 1){
            while(si<ss.length){
                if(ss[si] == ms[0]){
                    return si;
                }
                si++;
            }
            return -1;
        }
        int[] indexs = getIndex(ms);
        while(si<ss.length&&mi<ms.length){
            if (ss[si] == ms[mi]) {
                si++;
                mi++;
            }else if(indexs[mi] == -1) {
                si++;
            } else {
                mi = indexs[mi];
            }
        }
        return mi == ms.length?si-mi:-1;

    }

    public int[] getIndex(char[] chars){
        int[] indexs = new int[chars.length];
        indexs[0] = -1;
        indexs[1] = 0;
        int pos = 2;
        int cn = 0;
        while(pos<indexs.length){
            if(chars[cn] == chars[pos-1]){
                indexs[pos++] = ++cn;
            } else if(indexs[cn] != -1) {
                cn = indexs[cn];
            } else {
                pos++;
            }
        }

        return indexs;
    }
}
